#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e4+10;
int n,m,sq,a[MAXN],ans[MAXN],last[MAXN],pos[MAXN],tim,tot,cnt,now,l=1,r,buc[1000010];
struct query
{
	int l,r,tim,num;
	bool operator<(const query b)const
	{
		return pos[l]==pos[b.l]?(pos[r]==pos[b.r]?tim<b.tim:pos[r]<pos[b.r]):pos[l]<pos[b.l];
	}
}qu[MAXN];
struct rep
{
	int x,y,last;
}re[1010];
void insert(int x)
{
	if(!buc[x])++cnt;
	++buc[x];
	return;
}
void del(int x)
{
	if(buc[x]==1)--cnt;
	--buc[x];
	return;
}
int main()
{
	scanf("%d%d",&n,&m);
	sq=sqrt(n);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&a[i]);
		last[i]=a[i];
		pos[i]=(i-1)/sq+1;
	}
	for(int i=1;i<=m;++i)
	{
		char t1[5];
		int t2,t3;
		scanf("%s",t1);
		scanf("%d%d",&t2,&t3);
		if(t1[0]=='Q')qu[++tot]=(query){t2,t3,tim,tot};
		else
		{
			re[++tim]=(rep){t2,t3,last[t2]};
			last[t2]=t3;
		}
	}
	sort(qu+1,qu+1+tot);
	for(int i=1;i<=tot;++i)
	{
		while(now<qu[i].tim)
		{
			++now;
			int x=re[now].x;
			if(l<=x&&x<=r)
			{
				insert(re[now].y);
				del(a[x]);
			}
			a[x]=re[now].y;
		}
		while(now>qu[i].tim)
		{
			int x=re[now].x;
			if(l<=x&&x<=r)
			{
				insert(re[now].last);
				del(a[x]);
			}
			a[x]=re[now].last;
			--now;
		}
		while(r<qu[i].r)
		{
			++r;
			insert(a[r]);
		}
		while(l>qu[i].l)
		{
			--l;
			insert(a[l]);
		}
		while(r>qu[i].r)
		{
			del(a[r]);
			--r;
		}
		while(l<qu[i].l)
		{
			del(a[l]);
			++l;
		}
		ans[qu[i].num]=cnt;
	}
	for(int i=1;i<=tot;++i)
		printf("%d\n",ans[i]);
	return 0;
}
